use std::cmp::Ordering;

struct SortedArray<T> {
    data: Vec<T>,
    cmp_func: Box<dyn Fn(&T, &T) -> Ordering>,
}

impl<T> SortedArray<T> {
    fn new(cmp_func: Box<dyn Fn(&T, &T) -> Ordering>) -> Self {
        SortedArray {
            data: Vec::new(),
            cmp_func,
        }
    }

    fn insert(&mut self, value: T) {
        let index = match self.data.binary_search_by(|x| (self.cmp_func)(x, &value)) {
            Ok(index) => index,
            Err(index) => index,
        };
        self.data.insert(index, value);
    }

    fn index_of(&self, value: &T) -> Option<usize> {
        match self.data.binary_search_by(|x| (self.cmp_func)(x, value)) {
            Ok(index) => Some(index),
            Err(_) => None,
        }
    }

    fn remove(&mut self, index: usize) {
        if index < self.data.len() {
            self.data.remove(index);
        }
    }

    fn clear(&mut self) {
        self.data.clear();
    }
}

fn main() {
    let cmp_func = Box::new(|a: &i32, b: &i32| a.cmp(b));
    let mut array = SortedArray::new(cmp_func);

    array.insert(5);
    array.insert(1);
    array.insert(3);

    println!("{:?}", array.data); // [1, 3, 5]

    if let Some(index) = array.index_of(&3) {
        println!("Index of 3 is {}", index); // Index of 3 is 1
    }

    array.remove(1);
    println!("{:?}", array.data); // [1, 5]

    array.clear();
    println!("{:?}", array.data); // []
}
